\documentclass[]{beamer}
% vim: set expandtab spell:

\setbeamercovered{transparent}
% This file is a solution template for:

% \setbeamertemplate{navigation symbols}{} 

% - Talk at a conference/colloquium.
% - Talk length is about 20min.
% - Style is ornate.

%\usetheme{AnnArbor}
%\usetheme{Antibes}
%\usetheme{Bergen} % NAO
%\usetheme{Berkeley} % NAO
%\usetheme{Berlin}
%\usetheme{Boadilla}
%\usetheme{boxes} % NAO
%\usetheme{CambridgeUS}
%\usetheme{Copenhagen}
%\usetheme{Darmstadt} % QUASE
%\usetheme{default} % NAO
%\usetheme{Dresden}
%\usetheme{Frankfurt}
%\usetheme{Goettingen} % not bad, but not for this
%\usetheme{Hannover}
%\usetheme{Ilmenau} % BOM
%\usetheme{JuanLesPins}
%\usetheme{Luebeck}
\usetheme{Madrid}
%\usetheme{Malmoe}
%\usetheme{Marburg}
%\usetheme{Montpellier}
%\usetheme{PaloAlto} % nao com este logo
%\usetheme{Pittsburgh}
%\usetheme{Rochester} % QUASE
%\usetheme{Singapore} % NICE
%\usetheme{Szeged}
%\usetheme{Warsaw}

% Copyright 2004 by Till Tantau <tantau@users.sourceforge.net>.
%
% In principle, this file can be redistributed and/or modified under
% the terms of the GNU Public License, version 2.
%
% However, this file is supposed to be a template to be modified
% for your own needs. For this reason, if you use this file as a
% template and not specifically distribute it as part of a another
% package/program, I grant the extra permission to freely copy and
% modify this file as you see fit and even to delete this copyright
% notice. 


%\mode<presentation>
%{
%  \usetheme{Warsaw}
%  % or ...
%
%  \setbeamercovered{transparent}
%  % or whatever (possibly just delete it)
%}


%\usepackage[portuges]{babel}
\usepackage[utf8]{inputenc}

\usepackage{epstopdf}
\usepackage[]{graphicx}

\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage{ae}
\usepackage{proof,amsmath, amsthm, amssymb, txfonts, calc, mdwlist, stmaryrd,verbatim,  hyperref, fancybox}
\newcommand{\bnu}{\boldsymbol{\nu}}

\newcommand{\lts}[1]{\stackrel{\small{#1}}{\longrightarrow}}
%\usepackage{mathpartir}

\title[] % (optional, use only with long paper titles)
{15-740 Project: Analyzing Branch Mispredictions\\ (Milestone 3)}

%\subtitle
%{Include Only If Paper Has a Subtitle}

\author[Branch Mispredictions]{Bernardo Toninho, Ligia Nistor, Filipe Milit\~{a}o}
\institute[15-740 Class Project]
%\institute[CMU \& FCT-UNL] % (optional, but mostly needed)
%{
%Carnegie Mellon University \& Universidade Nova de Lisboa
%}
% - Use the \inst command only if there are several affiliations.
% - Keep it simple, no one is interested in your street address.

% If you have a file called "university-logo-filename.xxx", where xxx
% is a graphic format that can be processed by latex or pdflatex,
% resp., then you can add a logo as follows:

%\pgfdeclareimage[width=2cm]{university-logo}{fct}
%\logo{\pgfuseimage{university-logo}}


% Delete this, if you do not want the table of contents to pop up at
% the beginning of each subsection:
%\AtBeginSubsection[]
%{
%  \begin{frame}<beamer>
%    \frametitle{Percurso}
%    \tableofcontents[currentsection,currentsubsection]
%  \end{frame}
%}


% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

%\beamerdefaultoverlayspecification{<+->}


\begin{document}
\maketitle

\begin{frame}
\frametitle{Introduction}

\begin{block}{Analyzing Branch Mispredictions}
We use several techniques to study mispredictions and potentially
gather insights into why predictors fail and how they can be improved:
\begin{itemize}
\item Branch Classification
\item Correlated Prediction Identification
\item Misprediction Clustering
\end{itemize}
\end{block}

\end{frame}



\begin{frame}
\frametitle{Branch Classification}
\begin{block}{Branch Classification}
\begin{itemize}
\item Classify branches in a trace according to their taken behavior:
\begin{itemize}
\item Static branches (always and never taken)
\item Loop branches
\item Strict patterns ($0^n1^m$)
\item Block patterns (non-strict $0^n1^m$)
\item Complex patterns
\item Other
\end{itemize}
\item Cross-reference misprediction with branch classification data
\item Identify branch patterns that are not adequately captured by a
  predictor
\begin{itemize}
\item Potential improvement using a specialized predictor (hybrid)
\item Adapt to special cases
\end{itemize}
\end{itemize}
\end{block}

\end{frame}

\begin{frame}
\frametitle{Branch Classification}
Due to time constraints, we capped after 1000 branches:

\begin{center}
{\footnotesize
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
Trace & Always & Never & Loops & Strict & Block & Complex & Other\\\hline 
CLIENT & 42.90\% & 44.50\% & 1.20\% & 2.60\% & 0.00\% & 0.10\% & 8.70\%\\
INT & 23.85\% & 68.17\% & 1.69\% & 2.25\% & 0.45\% & 0.00\% & 3.60\%\\
MM & 18.85\% & 44.73\% & 6.07\% & 4.47\% & 0.64\% & 0.00\% & 25.24\% \\
SERVER & 27.50\% & 57.10\% & 4.20\% & 2.60\% & 0.90\% & 0.00\% & 7.70\%\\
WS & 8.33\% & 18.75\% & 25.00\% & 0.00\% & 0.00\% & 0.00\% & 47.92\%\\
\hline
\end{tabular}}
\end{center}
\end{frame}

\begin{frame}
\frametitle{Identifying Correlated Predictions}

\begin{block}{Idea}
\begin{itemize}
\item Predictors alias together multiple predictions
\item This aliasing might be constructive (e.g. branches with same
  history behaving similarly) or destructive (e.g. same history,
  completely different path through the program).
\item Can we distinguish the positive from the negative aliases?
\begin{itemize}
\item Successively decompose a predictor (gshare) into less aliasing
  versions
\item Determine sets of predictions that are aliased
\item Track the positive and negative effects of varying aliasing in
  these sets
\item Attempt to characterize these sets using available information
  (e.g. program context / stack depth).
\end{itemize}
\end{itemize}
\end{block}

\end{frame}

\begin{frame}
\frametitle{Identifying Correlated Predictions}
\begin{center}
WORK IN PROGRESS (no data yet...)
{\small
\begin{tabular}{|c|c|c|c|c|}
\hline
 & Positive & Negative & Partial & No. Sets \\\hline
gshare & & & &\\\hline
inf. size &&&&\\\hline
gselect &&&&\\\hline
path + history &&&&\\\hline
\end{tabular}}
\end{center}
\end{frame}

\begin{frame}
\frametitle{Correlated Predictions: Branch Outcome Stream}

\begin{block}{Idea}
\begin{itemize}
\item The predictor captures correlations between predictions
\item Actual predictions themselves depend on some form of $N$-bit counter\dots
\item How to determine if the counter's initial value is a determining
  factor in a substantial amount of predictions?
\begin{itemize}
\item Potentially motivates use of techniques to determine ``best''
  initial value.
\end{itemize}
\item How to determine how large should a counter be?
\item Our approach: Analyze the branch outcome streams for correlated predictions.
\end{itemize}

\end{block}

\end{frame}

\begin{frame}
\frametitle{Correlated Predictions: Branch Outcome Stream}
\begin{center}
{\small
\begin{tabular}{|c|c|c|c|c|}
\hline
Trace & Avg. Warm-up & \% Burst & Burst Flip \% & Avg. Trans. Length\\\hline
CLIENT03 & 3.000 & 2.381 & 0.000 & 2.086 \\
INT03 & 3.000 & 56.663 & 0.000 & 1.718\\
MM03 & 3.000 & 1.482 & 0.000 & 1.985\\
SERVER03 & NaN & 0.000 & NaN & 2.000\\
WS03 & 3.000 & 55.824 & 1.282 & 1.375\\
\hline
\end{tabular}}
\end{center}
\end{frame}

\begin{frame}
\frametitle{Correlated Predictions: Branch Outcome Stream}
If warm-up time is long means the initial value is inadequate!
\begin{block}{Determining Counter Size}
 How much of the stream is a burst (contiguous pattern at least twice)?
\begin{enumerate}
\item Low: A counter is not helpful, regardless of $N$ (counter is
  mostly late, at most 50\% accurate).
\item High: How often does the outcome of consecutive bursts change?
\begin{enumerate}
\item Often: A small $N$ is better (adapts quickly to change).
\item Infrequent: Consider the average transition length between bursts:
\begin{enumerate}
\item Need $N$ large enough to mask the transition length. 
\end{enumerate}
\end{enumerate}
\end{enumerate}
\end{block}
\end{frame}

\begin{frame}
\frametitle{Misprediction Clustering}

\begin{block}{Idea}
\begin{itemize}
\item Empirical data shows that mispredictions are far
  apart in time but\dots
\item Often we can observe clusters of contiguous mispredictions
\item Can we identify these clusters in a simple way and ``flip'' the
  wrong predictions? (i.e. prediction the mispredictions)
\item What gains, if any, can be obtained with this technique?
\end{itemize}
\end{block}

\end{frame}

\begin{frame}
\frametitle{Misprediction Clustering}

{\small
\begin{tabular}{|c|c|c|c|c|c|}
\hline
Trace & Avg. Misp. Cluster Size & gshare &  Optimal & Worst & gshare+ \\\hline
CLIENT & 2.971 & 2.276\% & 2.130\% & 2.280\% & 2.27\%\\
INT & 4.567 & 0.034\% & 0.020\% & 0.025\% & 0.034\% \\
MM & 5.081\% & 4.906\% & 5.246\% & 5.2\%\\
SERVER & 3.091 & 3.591\% & 3.165\% & 3.555\% & 3.52\%\\
WS & 2.366 & 16.866\% & 16.043\% & 18.495\% & 16.4\%
\end{tabular}}


\end{frame}


\begin{frame}
\frametitle{For the poster/final report}

Try to take into account context (find correlations sets).
How to identify the sets, what they have in common. Is only part of
the history relevant? path?
\end{frame}

\end{document}






\begin{frame}
\frametitle{Project Context}
\begin{block}{Branch Prediction}
	\begin{itemize}
	\item A fundamental component of
          micro-architectures: tries to \textit{predict} future paths to keep the pipeline full, avoid stalls.
        \item Misprediction penalty proportional to pipeline depth.
        \item Key constraints: needs to be \textbf{fast}, \textbf{simple} and
          \textbf{highly accurate}!
        \item Varied design space: local/global history based
          predictors, machine learning-based predictors, etc.    
	\end{itemize}
\end{block}
\pause
\begin{block}{Hybrid Branch Predictors}
	\begin{itemize}
	\item Each predictor has its own set of strengths/limitations.
	\item Idea: combine multiple predictors (try to get the
          ``best of both worlds'').
        \item Problem 1: What predictors should be combined? 
        \item Problem 2: How to dynamically choose between the component predictors to make the most accurate prediction?
	\end{itemize}
\end{block}
\end{frame}

\begin{frame}
\frametitle{Our Approach: Hybrid Predictor}

\begin{block}{Typical Hybrid Predictor}
\begin{itemize}
\item Combines two predictors: usually a global predictor and a ``specialized'' predictor
  (local predictor, loop predictor).
\item Decides using a PC-indexed table of 2-bit saturating counters.
%$${\scriptsize \mbox{PC}\rightarrow \mbox{ComponentDecisionTable}}$$
\end{itemize}
\pause
\end{block}
\begin{block}{A \textit{smarter} meta-predictor}
\begin{itemize}
\item Exploit additional information available to the meta-predictor:
\item[-] Index using a hash of the \textit{global history} and the \textit{PC}.
$${\scriptsize\overbrace{0101010..10101}^{\mbox{branch history}}  ~\oplus~ \mbox{PC}\rightarrow \mbox{ComponentDecisionTable}}$$
\item[-] Potentially allows the hybrid to choose more accurately between the two components, by exploiting inter-branch correlation.
\end{itemize}
\end{block}

\end{frame}

\begin{frame}
\frametitle{Evaluation Methodology}
\begin{block}{Simulation Infrastructure}
\begin{itemize}
\item Championship Branch Prediction (CBP) simulator.
\item Simple out-of-order 14 stage pipeline, 4-wide pipeline, 12-wide
  execution scheduler.
\item Outputs a very simple score based on misprediction penalty.
\item We extended the simulator with some customized statistics:
\begin{itemize}
\item Prediction progress ( mispredictions per branch execution );
\item Branch classification metrics ( taken percentage, transition frequency );
\item Branch trace ( how each prediction compares to the real behavior);
\end{itemize}
\end{itemize}
\end{block}
\pause
\begin{block}{Implemented Predictors}
\begin{itemize}
\item Baseline predictors: \textit{gshare}, \textit{perceptron}, \textit{o-gehl}, \textit{piecewise}, \textit{last}, \textit{always taken}, \textit{never taken}, \textit{random}, \textit{local};
\item Hybrids (with two variants for each meta-prediction scheme): gshare+local, perceptron+local, gshare+perceptron.
\end{itemize}
\end{block}
\end{frame}


\begin{frame}
\frametitle{Preliminary Results}
\begin{center}
\begin{tabular}{cc}
Misprediction Rates\\
%\includegraphics[scale=0.28]{aggregate}
\end{tabular}
\end{center}
\end{frame}



\begin{frame}
\frametitle{Preliminary Results}
\begin{center}
\begin{tabular}{cc}
Classifying Branches in Server Benchmark\\
%\includegraphics[scale=0.25]{classes_server02}
\end{tabular}
\end{center}
Most branches are never or rarely taken (history
doesn't help much here).
\end{frame}

\begin{frame}
\frametitle{Preliminary Results}
\begin{center}
\begin{tabular}{cc}
Classifying Wrong Predictions in Server Benchmark\\
%\includegraphics[scale=0.25]{wrong_server02}
\end{tabular}
\end{center}
44\% of the wrong predictions couldn't have been improved anyway\dots
\end{frame}

\begin{frame}
\frametitle{Preliminary Results}
\begin{block}{Wrong Decisions vs Optimal}
\begin{center}
{\tiny
% MM01 SEVER02
\begin{tabular}{| c | c | c || c | c | c |}
%% mm01
\hline
Test & Hybrid & Wrong Decisions & Miss Rate & Optimal & Difference \\
\hline
Multimedia & gshare + local(h1) & 34.0 \% & 7.4 \% & 2.9 \% & 4.5 \%\\
Multimedia & gshare + local(h2) & 27.3 \% & 6.5 \% & 2.9 \% & 3.6 \%\\
Multimedia & perceptron + local(h1) & 39.2 \% & 12.0 \% & 6.4 \% & 5.6 \% \\
Multimedia & perceptron + local(h2) & 34.5 \% & 10.9 \% & 6.4 \% & 4.5 \% \\
\hline
%%server02
Server & gshare + local(h1) & 24.8 \% & 2.8 \% & 1.4 \% & 1.4 \% \\
Server & gshare + local(h2) & 29.5 \% & 3.1 \% & 1.4 \% & 1.7 \%\\
Server & perceptron + local(h1) & 12.6 \% & 4.6 \% & 2.6 \% & 2.0 \%\\
Server & perceptron + local(h2) & 10.3 \% & 4.1 \% & 2.6 \% & 1.5 \%\\
\hline
\end{tabular}}\end{center}
\end{block}
\pause
\begin{block}{Summary}
\begin{itemize}
\item We performed similar analyses using different benchmark classes.
\item Overall, our hybrid scheme was mostly better than the
  existing one.
\item When it is worse, only slightly. Correlated non-typical branch
  behavior (as shown previously).
\end{itemize}
\end{block}

\end{frame}

\begin{frame}
\frametitle{Next milestone's goals}

\begin{itemize}
\item Compare with other predictors - namely this year's CBP winners
  (preliminary results show we are not quite there yet);
\item Further performance improvements - try to exploit the branch
  classification results to improve the meta-predictors;
\item Implementation fixes - some predictors do not behave as well as expected (\textit{o-gehl}, \textit{piecewise}, \textit{perceptron}) and need to be fixed;
\item Consistent decision on ``cheating'' - some implementations use a pseudo-cheat such as updating the branch history with the correct branch outcome at \textit{fetch} stage although such result is only known at \textit{retire} - but removing it yields poor performance inconsistent with the results in literature.
\end{itemize}

\end{frame}


\begin{frame}
\begin{center}
\begin{tabular}{cc}
Classifying Branches in Multimedia Benchmark\\
%\includegraphics[scale=0.25]{classes_mm01}
\end{tabular}
\end{center}
\end{frame}

\begin{frame}
\begin{center}
\begin{tabular}{cc}
Branch Re-execution Distribution in Server\\
%\includegraphics[scale=0.25]{distribution_server02}
\end{tabular}
\end{center}
\end{frame}